FLOW7 试题库问题

模型：

二分图多重匹配->网络最大流

题意：

假设一个试题库中有 $n$ 道试题。每道试题都标明了所属类别。同一道题可能有多个类别属性。现要从题库中抽取 $m$ 道题组成试卷。并要求试卷包含指定类型的试题。试设计一个满足要求的组卷算法。

题解：

代码：

#include <bits/stdc++.h>
using namespace std;
template<class t> inline t read(t &x){
    x=0;char c=getchar();bool f=0;
    while(!isdigit(c)) f|=c=='-',c=getchar();
    while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
    if(f) x=-x;return  x;
}
template<class t> inline void write(t x){
    if(x<0){putchar('-'),write(-x);}
    else{if(x>9)write(x/10);putchar('0'+x%10);}
}

const int oo=0x3f3f3f3f;
const int N=2050,M=1e6+5;
int en=1,h[N],d[N],n,m,s,t,use,cur[N],ans,tot;
bool v[N];

struct edge{
    int n,v,f;
}e[N+M<<1];

void add(int x,int y,int z){
    e[++en]=(edge){h[x],y,z};
    h[x]=en;
}

void exadd(int x,int y,int z){
    add(x,y,z);
    add(y,x,0);
}

bool bfs(int s,int aim){
    memset(d,0,sizeof d);
    memcpy(cur,h,sizeof cur);
    queue<int> q;
    q.push(s);
    d[s]=1;
    while(!q.empty()){
        int x=q.front();
        q.pop();
        for(int i=h[x];i;i=e[i].n){
            int y=e[i].v;
            if(d[y]==0&&e[i].f){
                d[y]=d[x]+1;
                if(y==aim) return 1;
                q.push(y);
            }
        }
    }
    return 0;
}

int dfs(int x,int flow,int aim){
    if(x==aim) return flow;
    int rest=flow;
    for(int &i=cur[x];i&&rest;i=e[i].n){
        int y=e[i].v;
        if(d[y]==d[x]+1&&e[i].f){
            int flow=dfs(y,min(rest,e[i].f),aim);
            rest-=flow;
            e[i].f-=flow;
            e[i^1].f+=flow;
        }
    }
    return flow-rest;
}

int dinic(int s,int t){
    int res=0;
    while(bfs(s,t)) res+=dfs(s,oo,t);
    return res;
}

signed main(){
    read(m);read(n);
    s=1,t=n+m+2;
    for(int i=1,x;i<=m;i++)
        exadd(i+s+n,t,read(x)),tot+=x;
    for(int i=1,nm;i<=n;i++){
        exadd(s,i+s,1);
        read(nm);
        for(int j=1,x;j<=nm;j++)
            exadd(i+s,read(x)+s+n,1);
    }
    if(dinic(s,t)^tot){
        printf("No Solution!");
        return 0;
    }
    for(int i=1;i<=m;i++){
        if(i^1) puts("");
        write(i);putchar(':');
        int x=i+s+n;
        for(int i=h[x];i;i=e[i].n) if(e[i].f){
            putchar(' ');
            write(e[i].v-s);
        }
    }
}